package com.ken.algorithms.tree;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;

/**
 * <ul>
 * <li>Title: LC114Main</li>
 * <li>Description: TODO </li>
 * </ul>
 *
 * @author swc
 * @date 2021-09-15 17:39
 */
public class LC114Main {


    /**
     1
     / \
     2   5
     / \   \
     3   4   6
        / \
       0 16

     1 2 5
     2 3 4
     3 0 0
     4 0 16
     16 0 0
     5 0 6
     6 0 0
     * @param args
     * @return: void
     * @author: swc
     * @date: 2021-09-15 17:45
    */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("输入节点总数和根节点总数:");
        sc.nextLine(); // 第一行没啥用
        TreeNode root = TreeUtil.createTreeNode(sc);

        List<TreeNode> list = createList(root);
        for (TreeNode treeNode : list) {
            System.out.print(treeNode.getVal());
        }

    }


    /**
     * 功能描述: 生成单链表
     * @param root
     * @return: java.util.List<com.ken.algorithms.tree.TreeNode>
     * @author: swc
     * @date: 2021-09-15 17:40
    */
    private static List<TreeNode> createList(TreeNode root) {
        if(root==null){
            return null;
        }

        List<TreeNode> list = new ArrayList<TreeNode>();
        Stack<TreeNode> stack =new Stack<>();

        TreeNode cur =root;
        while (cur!=null || !stack.isEmpty()){
            if(cur!=null){
                stack.push(cur);
                list.add(cur);
                cur = cur.getLeft();//先遍历左侧节点
            }else{//处理的是右节点
                cur = stack.pop(); //当左侧节点为空 移除栈顶元素
                cur = cur.getRight();
                //再把右节点的值赋值于当前操作节点 如果右节点不为空则加入栈顶【当然他父节点已被移除了】
                // 如果为空把它也移除 最终会找到它含有右节点的父节点 最终父（父）节点会移掉 取而代之是非空的右侧节点
            }
        }
        return list;
    }
}
